import java.util.*;
 class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
public class Partition {
    public ListNode partition(ListNode pHead, int x) {
        // write code here
        ListNode curB = null;
        ListNode curL = null;
        ListNode cur = pHead;
        ListNode newHead1 = null;
        ListNode newHead2 = null;

        while (cur != null) {
            if (cur.val < cur.val) {
                if (curL == null) {
                    curL = cur;
                    newHead1 = cur;
                }else {
                    curL.next = cur;
                    curL = cur;
                }
            }else {
                if (curB == null) {
                    curB = cur;
                    newHead2 = cur;
                }else {
                    curB.next = cur;
                    curB = cur;
                }
            }
            cur = cur.next;
        }
        if (curL == null || curB == null) {
            return pHead;
        }
            curB.next = null;
            curL.next = null;
            curL.next = newHead2;
            return newHead1;
    }
}